class ListNode:
    def __init__(self, x, next=None):
        self.val = x
        self.next = next

def print_list(head):
    while head:
        print(head.val, end=', ')
        head = head.next
    print('\n'+'-'*10)

class Solution:

    def __init__(self) -> None:
        self.FirstCommonNode = None

        self.visied = []

    

    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        self.visied = []
        while pHead1:
            self.visied.append(pHead1)
            pHead1 = pHead1.next
        while pHead2:
            if pHead2 in self.visied:
                return pHead2
            pHead2 = pHead2.next


if __name__ == '__main__':
    print("两个链表的第一个公共结点")
    print("method1: 先遍历list1, 把遍历的节点都放到数组，然后遍历2,依次是否存在于数组，第一个发现存在的就是第一个公共节点")
    print("method2: 先遍历2个list，得到长度差值x。然后让长的先走x步，然后2个一起走，第一次相遇就是公共节点")
    print("method3: 让list1、list2同时开始走，谁先到头(null)，则重新从对方list的头再次开始，直到2个第一次相遇")
    print("method3相当于是把1，2连起来了\n")
    print("method1是最愚蠢的，method2是最常规的，我只想到了愚蠢的，连常规的都没第一下想到，气死\n")
    common = ListNode(10, ListNode(11, ListNode(12)))
    head1 = ListNode(1, ListNode(2, ListNode(3, common)))
    head2 = ListNode(4, ListNode(5, ListNode(6, common)))
    print_list(head1)
    print_list(head2)
    first = Solution().FindFirstCommonNode(head1, head2)
    print_list(first)
    